import java.util.ArrayList;
import java.util.List;

public class Test25 {
    public static List<Integer> path = new ArrayList<>();
    public static void findPath(TreeNode root,int n){
        if (root != null){
            BFS(root,0,n);
        }
    }
    public static void BFS(TreeNode root,int curnum,int n){
        if (root == null) return;
        curnum += root.val;
        path.add(root.val);
        if (curnum < n){
            if (root.left != null) BFS(root.left,curnum,n);
            if (root.right != null) BFS(root.right,curnum,n);
        }else if (curnum == n) {
            if (root.right == null && root.left == null) {
                System.out.println(path);
            }
        }
        path.remove(path.size()-1);

    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode();
        root.val = 1;
        root.left = new TreeNode();
        root.left.val = 2;
        root.right = new TreeNode();
        root.right.val = 3;
        root.left.left = new TreeNode();
        root.left.left.val = 4;
        root.left.right = new TreeNode();
        root.left.right.val = 5;
        root.right.left = new TreeNode();
        root.right.left.val = 6;
        root.right.right = new TreeNode();
        root.right.right.val = 7;
        findPath(root,10);
    }
}
